<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<html>



<head>

<title> Lab 3 </title>

<style>

	* {

		font-size:18pt;

	}

</style>

</head>



<body>



<h1> Lab 3: A &quot;Flat&quot; File Directory for a File System Based on BlockGroup's</h1>

<h2>Team Lab #2 </h2>

<p>CS 5631, Fall 2012<br>

  <strong>Doxygen  for Design</strong> Due Wed, October 10 (8 points) <br>

  <strong>C++ Program</strong> Due Wed, October 17 (22 points)</p>

<p><a href="grading_scheme_lab3.doc">DRAFT of Lab 3 grading scheme</a>. This will likely be revised before the labs are graded!!!</p>

<hr>



<h3><em><strong>Revisions</strong></em></h3>

<blockquote>

  <p>10/3/12; 2pm; Added sentence requiring submission of Doxygen in HTML format.</p>

</blockquote>

<h3>Introduction </h3>

<blockquote>

  <p>In this lab you will continue with the  File System you have been constructing. So far (in File System Lab 1), you have created   a FreeList class that lets you keep track of  unused blocks on the Disk and a BlockGroup class that lets you organize other disk blocks into groups. You  have likely  noticed that so far we are only keeping track on Disk  (i.e., in the master block) of location information about the FreeList (the start block number, end block number and number of blocks). That is, we have not yet been storing location information on Disk about BlockGroup's.  In this lab, you will be creating a <strong><em>Directory</em></strong> class, and any other support classes that you find useful, in order to eventually do this (store start block number, end block number, and number of blocks for BlockGroups to Disk).</p>

  <p>Your Directory will contain <em>_files_</em>. Each _file_  will keep track of two pieces of information. One of the pieces of information in a _file_ will be a name-- these will be used later (in File System Lab 3) as file names. The other piece of information that you will include in a _file_ will be the block number for the <em>File Control Block</em> for the file. The File Control Block will contain the start block number, end block number, and number of blocks for the BlockGroup that represents a file. Your  Directory should be &quot;flat&quot;. <strong>This will mean that  your Directory will not contain sub-directories. </strong>While sub-directories are useful, they require a  more complex implementation than a &quot;flat&quot; directory. One consequence of using a &quot;flat&quot; directory is that you will maintain only a single (one) directory on Disk. </p>

</blockquote>

<p><strong>Resources</strong></p>

<blockquote>

  <p>Chapters 9 and 10 of our course text. </p>

  <blockquote>

    <p>I strongly recommend you read these to prepare for this lab. In particular, you should  read Section 9.3 on Single-Level Directories. </p>

  </blockquote>

  <p><a href="http://www.doxygen.org/">General Doxygen reference</a></p>

  <p><a href="http://www.stack.nl/~dimitri/doxygen/docblocks.html">Doxygen reference on commenting</a></p>

  <p><a href="../lab2/html/annotated.html">Doxygen documentation for the BlockGroup, FreeList, BlockLinkedList, Block, and Disk classes.</a></p>

  <p><a href="http://valgrind.org/">Valgrind: A tool to find memory leaks.</a></p>

  <p>Some Unix man pages for directory accessing. These only provide reading, not modifying-- you need to think about modification operations. Also: Don't take these too literally. They are specific to Unix, and yours can be simpler and/or more elegant!!</p>

  <blockquote>

    <p><a href="http://manpages.courier-mta.org/htmlman3/opendir.3.html">opendir</a></p>

    <p><a href="http://manpages.courier-mta.org/htmlman3/readdir.3.html">readdir</a></p>

    <p><a href="http://manpages.courier-mta.org/htmlman3/scandir.3.html">scandir</a></p>

    <p><a href="http://manpages.courier-mta.org/htmlman3/closedir.3.html">closedir</a></p>

  </blockquote>

</blockquote>

<p><strong>Some details</strong></p>

<blockquote>

  <p id="binary"><em>Required binary format for file system</em></p>

  <blockquote>

    <p>(1) <a href="../lab2/#binary">See the binary format requirements for the Free List, Block Linked List and Master Block.</a> These are still required.</p>

    <p>(2) The master block now needs four additional four byte binary unsigned integer values, in this order, after the current information about the FreeList: </p>

    <blockquote>

      <p>a) start block number of the Directory BlockGroup,</p>

      <p>b) end block number of the Directory BlockGroup,</p>

      <p>c) number of blocks in the Directory BlockGroup,</p>

      <p>d) number of files in the Directory.</p>

    </blockquote>

    <p>(3) As before, store binary integer values on disk in network byte order (big endian byte order) using the ntohl and htonl functions.</p>

    <p id="DIRBINARY">(4) Each _file_ will have the following format, in this order:</p>

    <blockquote>

      <p>a) A file name with at most 123 bytes including a 0 byte (NULL) terminator. That is, the text of the file name will have at most 122 characters. A 0 byte must be written to the _file_ to mark the end of the file name. (NOTE: It seems reasonable to use NULL termination for file names, because we have no reason to have file names include NULL bytes, i.e., file names are not binary).</p>

      <p>b) A four byte unsigned binary integer giving the block number (stored in network byte order) of the FCB (File Control Block) for the file.</p>

      <p>c) Thus, each _file_ is exactly 127 bytes, and at most four _files_ will be stored in each block of the Directory BlockGroup.</p>

      <p>d) _files_ are stored consecutively within blocks of the Directory BlockGroup. For example, if there is only one _file_, it will be stored immediately after the &quot;next pointer&quot; of the first block of the Directory BlockGroup, and if there are two blocks, they will be stored immediately adjacent to each other in the Disk block, leaving room for two more _files_ in the remaining bytes of the Disk block.</p>

    </blockquote>

    <p>(5) File Control Blocks: Don't yet allocate these from the FreeList yet. Just initialize the FCB reference in each _file_ to some non-random non-zero value (e.g., 10), and in the next lab we will start to use these entries. </p>

 

  </blockquote>

  <p><em>Documentation for  C++ Classes</em></p>

  <blockquote>

    <p>I won't be giving you my  documentation for my solution this time around. Instead, your first goal in this lab is to  come up with a written design for your Directory class API ('application' programming interface). The structure you will follow for this design will be  Doxygen. For some information on how to format your C++ code to be suited to Doxygen, see the Resources section above.</p>

    <p>By using Doxygen, I mean that you will be creating &quot;stub&quot; code for your classes and documenting this stub code. &quot;Stub&quot; code contains the names of all methods and classes, as well as the parameters for all methods, but none of the methods need to have code written in the method bodies. Also, the data members of the classes do not need to be defined yet (except perhaps for the DirectoryEntry class-- see below). Your design will be submitted one week before the C++ program code solution for the lab. See due dates above, and see submission at the bottom of this page. </p>

  </blockquote>

  <p><em>What about the start and end block for my Directory BlockGroup?</em></p>

  <blockquote>

    <p>While you will use a BlockGroup to represent your Directory on Disk, and this Directory BlockGroup will store information for various other  BlockGroup's (actually, the Directory will store information about FCB's and the FCB's will store information about other BlockGroup's), there is, of course, the problem of storing the information about the Directory BlockGroup  (start block number, end block number, and number of blocks) itself! That is, the Directory is going to be represented as a BlockGroup, and therefore the Directory BlockGroup has start and end block numbers, and a number of blocks. Storing the start and end block numbers for the Directory will entail modifying the information stored in the master block. <em>That is, along with information about the location of the FreeList, information about the Directory  will be stored in the master block of the disk</em>.</p>

    <p>Implict in the fact that a Directory is a BlockGroup is the idea that your Directory may have more than one block in it. For example, if you are representing, say, 20 files, with our required binary format, you will need to represent five blocks in your Directory BlockGroup.</p>

    <p><em><a name="NumberOfEntries">Your</a> Directory must be capable of holding an arbitrary number of entries.</em> The limit on the number of entries should depend only on the number of disk blocks available on the Disk (i.e., in the FreeList  for the Disk). That is, you need to code your Directory so that it potentially can have lots of _files_ and those will naturally span multiple disk blocks.</p>

  </blockquote>

  <p><em>What information should I represent per &quot;file&quot; entry in the Directory?</em></p>

  <blockquote>

    <p>Later, you will be using your Directory implementation (in File System Lab 3) to keep track of information for BlockGroup's that are representing files of data, so you should think in those terms. The <a href="#DIRBINARY">binary requirements for _files_</a> require you to represent a file name, and and the block number of a File Control Block. </p>

    <p>I suggest you design and program a <em>DirectoryEntry</em> class to represent the data that will be in each _file_. I further suggest that each of the data members for the DirectoryEntry should be public-- this will just be a utility class (analogous to the Block class). You should submit Doxygen documentation for your DirectoryEntry class as part of your design.</p>

  </blockquote>

  <p><em>What about methods for the Directory class? What methods should I have?</em></p>

  <blockquote>

    <p>Well, this is one main thing you will need to  decide in your Doxygen-based design. Your Directory needs to let you deal with _files_, and must enable these to  be stored on Disk in the blocks of the BlockGroup associated with the Directory. You must be able to: 1) open the directory, 2) retrieve directory  entries from Disk, 3) search for a _file_ by  name (i.e., by file name), 4) save  entries to Disk, 5) delete a _file_, 6) rename a _file_, 7) add a _file_, and 8) close the directory. </p>

    <p>I recommend that you store all entries for a Directory in RAM during a &quot;session&quot; in which you are using the Directory. This is very different from the way you previously worked -- with the BlockGroup class and FreeList. In that case, you wanted to <em><strong>not</strong></em> store much of a BlockGroup or the FreeList in RAM. I'll repeat myself: In the case of the Directory, it seems reasonable to store all of the _files_ in RAM during a single session of using the Directory. Of course, you will need to provide methods that enable these (possibly changed) _files_ to be &quot;flushed&quot; to (synchronized with the) Disk. The assumption you will be making when you temporarily cache <em><strong>all</strong></em> of the entries for the Directory in RAM is that the total number of bytes for all combined _files_ is relatively small, and the number of entries will be relatively small (e.g., on the order of 10 to 100 files referenced from a directory). </p>

  </blockquote>

<p><em>STL</em></p>

<blockquote>

  <p>The erase method of STL vector does NOT call the destructor when you are using pointer objects. <a href="stdVector2.cpp">See this example.</a> You must call the destructor yourself before erasing when using pointer objects.</p>

</blockquote>

<p><em>Testing</em></p>

  <blockquote>

    <p>Use the same kind of menu driven testing as in the earlier labs. Make sure to be systematic in your testing. For example, make sure you test adding enough &quot;files&quot; (_files_) to make the Directory span multiple Disk blocks in the BlockGroup that represents the Directory, and also make sure to test deleting all of these &quot;files&quot;.</p>

    <p>Your testing must also include  writing the directory to the disk,  shutting down the file system program, then starting the program back up. You must then show that the contents of the directory are preserved.</p>

  </blockquote>

 



</blockquote>

<p><strong>Goal</strong></p>

<blockquote>Submit your design, by the due date for the design. Submit your working program code by the due date for the C++ code. 

  <p>After you implement a class (or even better, after implementing one or two methods for a class), write testing code to test the class, and carry out the testing and debugging. I code a static Test method in each class, and put my menu-driven testing code for the class in that method. When you write the C++ code for each of your classes   you should create menu driven testing (like in earlier labs) that provides testing of that class. </p>

</blockquote>

<blockquote>

  <p>Use proper software engineering style-- </p>

  <blockquote>

    <p>(a) Document your methods (Doxygen comments before each method indicating the purpose of the method), and document your program code that implements the methods.</p>

    <p>(b) Use named constants instead of numeric values where this improves readability (it usually does improves readability!!).</p>

    <p>(c) Use variable names and method names that have meaning in the context of the program you are writing.</p>

  </blockquote>

</blockquote>

<p>



<b id="submission">Submission</b>

<blockquote>

  <p>By the Design due date, <a href="https://moodle2.umn.edu/mod/assignment/view.php?id=847575">upload</a> your Doxygen (zipped). This should be the HTML version of the Doxygen output generated by a tool that supports Doxygen (e.g., <a href="http://www.stack.nl/~dimitri/doxygen/download.html#latestsrc">see these downloads</a>). [[This last sentence added on 10/3/12, 2pm]].</p>

  <p>For the Doxygen design, you will be graded on (a) having a complete set of methods that will enable use of a Directory and DirectoryEntry classes, and (b)  on your descriptions of your methods. In general, you need to provide clear and complete descriptions of the operations your methods will provide. You should attempt to anticipate (and document) the types of error situations, and reasons for these errors, that will occur when calling the methods you specify for the Directory class.  </p>

  <p>By the C++ program due date, turn in hardcopy (a printout) of your running program code (.cpp and .h files). Also turn in hardcopy of your testing output. Make sure to be systematic in your testing. If you have made changes to your earlier classes (e.g., Block, BlockGroup), turn in hardcopies of that  too (if you have made no changes to your  other classes, you don't need to turn it in again on hardcopy). </p>

  <blockquote>

    <p>Also, <a href="https://moodle2.umn.edu/mod/assignment/view.php?id=847575">upload</a> your C++ program  (.zip file of <em>all</em> the  program code and classes) by the due date.</p>

    <p>If you use Netbeans, be careful that when you zip up your files for   submission that you have included the source files. It can be easy for Netbeans   to have entirely separate directory locations for your project and your source   code. </p>

  </blockquote>

  <p>Each team should turn in just one submission, including both hardcopy (please, no line wrap on the code hardcopy output!!) and upload. Please submit a cover page on your hardcopy that includes all of the names   of the team members. For the program code you web drop, please ensure that each   of your program code files (i.e., the .cpp and .h files) have all of the names of the   team members. In a second page, please also submit a short written description of your lab work-- in this please describe any problems you have had in  the lab. For example, if your program is not fully working, please describe which parts of your program are working, which parts are not working, and describe the problems you encountered. This does not have to be a long description. A short paragraph would be fine.<em><strong> If your program is not working at all YOU MUST indicate that the program is not working in this short written description.</strong></em> If your program doesn't work, and you submit no testing, and you don't tell us this fact in the short written description, you will get a 0 for the lab.</p>

  <p>You must use this <a href="http://rattus.d.umn.edu/~cprince/cs5631/testing/lab3/fstest/">online file system testing method</a> to conduct some of the testing of your program, and submit printed results of the testing (browser page printouts). You must run at least the following three tests on your binary file system. Note that in each case the file control block numbers you use must be non-zero (but you are not yet allocating these FCB's).</p>

  <blockquote>

    <p>(1) where the directory has 0 files, </p>

    <p>(2) where the directory has 1 file, and </p>

    <p>(3) where it has 5 files. </p>

    <p>Here's an <a href="fstest/sample.jpg">example of some correct testing output</a>. You must adhere to the <a href="#binary">required binary format</a> of the file system for these tests to work.</p>

  </blockquote>

</blockquote>

<p> 

</body>



</html>



